package src.DisciplesPlan.链表;

/**
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
  

 示例 1：


 输入：head = [1,2,3,4,5]
 输出：[5,4,3,2,1]
 示例 2：


 输入：head = [1,2]
 输出：[2,1]
 示例 3：

 输入：head = []
 输出：[]
 */

public class _206反转链表 {
    public static void main(String[] args) {

    }

    public ListNode reverseList(ListNode head) {
        if (head == null)
            return head;
        // 新链表的头结点，并非头指针
        ListNode pre = null;
        // 遍历指针
        ListNode cur = head;
        // 遍历指针的下一个指针，防止链表断裂
        ListNode p = head.next;
        while (cur != null) {
            // 将当前结点用头插法插到新链表上
            cur.next = pre;
            pre = cur;
            // 指针后移
            cur = p;
            if (p != null) {
                p = p.next;
            }
        }
        return pre;
    }

    // 递归写法
    public ListNode reverseList1(ListNode head) {
        // 若当前结点或者下一个结点为空，直接返回当前结点
        if (head == null || head.next == null)
            return head;
        // 不断递归向后移动双指针直到标记到尾结点和倒数第二个结点
        ListNode tail = head.next;
        ListNode p = reverseList1(head.next);
        // 依次取最后两个结点将其反转
        head.next = tail.next;
        tail.next = head;
        // 返回原链表的尾结点，也即反转后的链表的头结点，注意:每一层返回的p结点都是同一个结点
        return p;
    }
}
